import reda.helpers.Helper;

/**
 * 
 */

/**
 * @author reda
 *
 */
public class QuickSort {
	
	public int[] input;
	public int[] result;
	
	public QuickSort(int[] input){
		this.input = input;
		this.result = new int[input.length];
	}

	public void quickSort(int low, int high){
		if(low>=high){
			return;
		}
		int pivot = (high+low)/2;
		int i = low, j = high;
		while(i<=pivot && j>=pivot){
			while (i<pivot && j>pivot && input[i]>input[pivot] && input[j]<input[pivot]){
				exchange(input,i,j);i++;j--;
			}
			while(i<=pivot && input[i]<=input[pivot]){
				i++;
			}
			while(j>=pivot && input[j]>=input[pivot]){
				j--;
			}
		}
		while(i<pivot && input[i]>input[pivot]){
			exchange(input,i,pivot-1);
			exchange(input,pivot-1,pivot);
			pivot--;
			if(input[i]<input[pivot]){
				i++;
			}
			
			
		}
		while(j>pivot && input[j]<input[pivot]){
			System.out.println("----"+j);
			exchange(input,j,pivot+1);
			exchange(input,pivot+1,pivot);
			pivot++;
			if(input[j]>input[pivot]){
				j--;
			}
			
			
		}
		quickSort(low,pivot);
		quickSort(pivot+1,high);
	}
	
	private void exchange(int[] array, int i,int j){
		int temp = array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] inputArray = Helper.generateArray(10);
		System.out.println("Before Sort");
		QuickSort q = new QuickSort(inputArray);
		Helper.printer(inputArray);
		q.quickSort(0,inputArray.length-1);
		System.out.println("\n After Sort");
		Helper.printer(inputArray);
	}

}
